#include<string>
#include<vector>
#include<unordered_set>
#include<iostream>
using std::vector;
using std::string;
using std::unordered_set;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words;
        for (auto& s: wordDict) words.insert(s);
        vector<bool> dp(s.size() + 1, 0);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && check(s, i, j, words)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];

    }

    bool check(string& s, int i, int j, unordered_set<string>& wordDict) {
        return wordDict.find(s.substr(j, i-j)) != wordDict.end();
    }
};


int main() {
    string s;
    std::cin >> s;
    vector<string> wordDict;
    string temp;
    while(std::cin >> temp) wordDict.push_back(temp);
    std::cout << s << "\n";
    std::cout << "Dict\n";
    for (auto str: wordDict) std::cout << str << "\n";

    auto res = Solution().wordBreak(s, wordDict);
    std::cout << res;
}